package main
// coding: utf-8
// @Author : lryself
// @Date : 2020/10/17 14:36
// @Software: GoLand

// 题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回 n 皇后不同的解决方案的数量。
// 题目url：https://leetcode-cn.com/problems/n-queens-ii/
// 作者题解：https://leetcode-cn.com/problems/n-queens-ii/solution/shi-jian-100dan-shu-zu-zhi-zhen-de-hui-su-fen-zhi-/

import (
	"fmt"
	"go_learning/src/utils"
	"strings"
)


func main() {
	queenNums := 4
	e1 := solveNQueens
	utils.DecoratorExample(&e1,solveNQueens)
	fmt.Println(e1(queenNums))
}

var queensY = make([]int,0)

func solveNQueens(n int) [][]string {
	solution := [][]string{}
	var indexX int
	indexY := -1
	if n==0{
		return solution
	}
	for{
		if loadQueen(indexX,indexY,n){
			indexX++
			indexY = -1
			if indexX>=n{
				solution=append(solution, make_queens_slice(queensY))
				indexY = queensY[indexX-1]
				indexX = back_queen(indexX)
			}
		}else{
			if indexX == 0{
				if indexY>=n-1{
					return solution
				}
				continue
			}
			indexY = queensY[indexX-1]
			indexX = back_queen(indexX)
		}
	}
}
func loadQueen(x, oldY,n int)bool{
	for y:=oldY+1;y<n;y++{
		if verify(x,y){
			if len(queensY)>=x{
				queensY = append(queensY,y)
			}else{
				queensY[x] = y
			}
			return true
		}
	}
	return false
}
func verify(x,y int) bool{
	for i:=0; i<len(queensY);i++{
		if i==x{
			return false
		}else if queensY[i]==y{
			return false
		}else if float64(i-x)/float64(queensY[i]-y)==1.0 || float64(i-x)/float64(queensY[i]-y)==-1.0 {
			return false
		}
	}
	return true
}
func back_queen(indexX int)int{
	indexX--
	if indexX<0{
		queensY = []int{}
	}else{
		queensY = queensY[:len(queensY)-1]
	}
	return indexX
}


func make_queens_slice(solution []int) []string{
	result := []string{}
	for i:=0;i<len(solution);i++{
		result = append(result, strings.Repeat(string('.'),len(solution)))
	}
	for i,y := range solution{
		result[y]=result[y][:i]+"Q"+result[y][i+1:]
	}
	return result
}